| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170 |
- From tterribe@email.unc.edu Wed Mar 18 15:38:26 2009
- Return-Path: <ccan-bounces+rusty=rustcorp.com.au@ozlabs.org>
- X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on ozlabs.org
- X-Spam-Level:
- X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham
- version=3.2.5
- X-Original-To: rusty@rustcorp.com.au
- Delivered-To: rusty@ozlabs.org
- Received: from ozlabs.org (localhost [127.0.0.1])
- by ozlabs.org (Postfix) with ESMTP id 5399ADDE0E
- for <rusty@rustcorp.com.au>; Thu, 19 Mar 2009 09:38:11 +1100 (EST)
- X-Original-To: ccan@ozlabs.org
- Delivered-To: ccan@ozlabs.org
- X-Greylist: delayed 2513 seconds by postgrey-1.31 at ozlabs;
- Wed, 18 Mar 2009 16:50:38 EST
- Received: from mxpm.isis.unc.edu (mxp3.isis.unc.edu [152.2.2.161])
- by ozlabs.org (Postfix) with ESMTP id 72C75DDEFA
- for <ccan@ozlabs.org>; Wed, 18 Mar 2009 16:50:37 +1100 (EST)
- Received: from smtp.unc.edu (smtpsrv3.isis.unc.edu [152.2.2.251])
- by mxp3.isis.unc.edu (8.14.3/8.14.3) with ESMTP id n2I58gVL008719
- for <ccan@ozlabs.org>; Wed, 18 Mar 2009 01:08:42 -0400
- Received: from [192.168.5.124] (pool-173-73-173-234.washdc.fios.verizon.net
- [173.73.173.234]) (authenticated bits=0)
- by smtp.unc.edu (8.14.3/8.14.3) with ESMTP id n2I58fex014904
- (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT)
- for <ccan@ozlabs.org>; Wed, 18 Mar 2009 01:08:42 -0400 (EDT)
- Message-ID: <49C081CA.5040501@email.unc.edu>
- Date: Wed, 18 Mar 2009 01:08:26 -0400
- From: "Timothy B. Terriberry" <tterribe@email.unc.edu>
- User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US;
- rv:1.8.1.11) Gecko/20071216 SeaMonkey/1.1.7
- MIME-Version: 1.0
- To: ccan@ozlabs.org
- References: <c3cfaf5e0901190756x569da515s823fe4c7bd99c22a@mail.gmail.com>
- <200902040051.54761.rusty@rustcorp.com.au>
- <c3cfaf5e0902051926m6a2793e5pfdef62040becb4e7@mail.gmail.com>
- <200903181452.14263.rusty@rustcorp.com.au>
- In-Reply-To: <200903181452.14263.rusty@rustcorp.com.au>
- Content-Type: multipart/mixed;
- boundary="------------050107030903080507030408"
- X-Proofpoint-Virus-Version: vendor=fsecure engine=1.12.7400:2.4.4, 1.2.40,
- 4.0.166 definitions=2009-03-18_01:2009-03-13, 2009-03-18,
- 2009-03-17 signatures=0
- X-Proofpoint-Spam-Details: rule=uncdefault_notspam policy=uncdefault score=0
- spamscore=0 ipscore=0 phishscore=0 bulkscore=0 adultscore=0
- classifier=spam adjust=0 reason=mlx engine=5.0.0-0811170000
- definitions=main-0903170259
- X-Mailman-Approved-At: Thu, 19 Mar 2009 09:38:09 +1100
- Subject: Re: [ccan] Mathematics Module
- X-BeenThere: ccan@ozlabs.org
- X-Mailman-Version: 2.1.11
- Precedence: list
- List-Id: "If perl can, maybe ccan?" <ccan.ozlabs.org>
- List-Unsubscribe: <https://ozlabs.org/mailman/options/ccan>,
- <mailto:ccan-request@ozlabs.org?subject=unsubscribe>
- List-Archive: <http://ozlabs.org/pipermail/ccan>
- List-Post: <mailto:ccan@ozlabs.org>
- List-Help: <mailto:ccan-request@ozlabs.org?subject=help>
- List-Subscribe: <https://ozlabs.org/mailman/listinfo/ccan>,
- <mailto:ccan-request@ozlabs.org?subject=subscribe>
- Sender: ccan-bounces+rusty=rustcorp.com.au@ozlabs.org
- Errors-To: ccan-bounces+rusty=rustcorp.com.au@ozlabs.org
- Status: R
- X-Status: NT
- X-KMail-EncryptionState:
- X-KMail-SignatureState:
- X-KMail-MDN-Sent:
- This is a multi-part message in MIME format.
- --------------050107030903080507030408
- Content-Type: text/plain; charset=ISO-8859-1
- Content-Transfer-Encoding: 7bit
- Some of this stuff seems a little trivial to include, but if we're going
- to do so...
- The result of nCr is guaranteed to be an integer after each iteration,
- and so there's a) no reason to keep a separate numerator and denominator
- and b) no reason to do a minimum of nine (9!) divisions every iteration.
- Only a single gcd() is needed, and even that can often be skipped,
- requiring only 2-3 divisions per iteration. This is illustrated in
- choose.c (attached). You can easily add the check for the smaller r (_m
- in this implementation), upgrade the types to long, etc., as desired. If
- one really cared about speed, the divisions could be entirely replaced
- by multiplications and a small lookup table, since m and n are known to
- have a very limited range (or the result will overflow).
- Also included are a gcd() implementation without tail recursion and
- egcd(), the "extended" gcd, as well as a nice illustration of the use of
- egcd, a Chinese Remainder Theorem solver for systems of linear
- congruences. I don't have time to format these into a nice module with
- test cases right now, but feel free to take what you want and throw the
- rest in "junk". The code is (C) 1998-2001, except crt.c, which is (C)
- 1999-2001, 2007. I'm releasing it here under the LGPLv2 license.
- --------------050107030903080507030408
- Content-Type: application/x-bzip;
- name="nmbrthry.tar.bz2"
- Content-Transfer-Encoding: base64
- Content-Disposition: inline;
- filename="nmbrthry.tar.bz2"
- QlpoOTFBWSZTWdZHi4IAD0t/nv/QAEB7//+/u2e8i//v/+4AQAAIAAGEgAAIYA798qVUUAAX
- YNLYVbSAAAKUAAKAAAAcGQaNAGTTENNBkGIYQNAaMTEaAAAaCjTEBIHqAADT1D1AAGgAAAAA
- HBkGjQBk0xDTQZBiGEDQGjExGgAAEmpFNRlNT/RGVN5U2mptT2qabUNqBiAyAADI8o09Eaeo
- cGQaNAGTTENNBkGIYQNAaMTEaAAAKkgggjQEZAQ0Mk0jU8U9Gmo0eU9TxpQZkaMjU2p9kDMf
- V9wivZ4gOTqn7wGbkUSRyyEA29t22fDfGfQl4fTBxbWtte1ra3VtnHjpqhvvQpVKhSqEVIKR
- LJUUqJKoTo/kUfaDk4lVemwZOWUGotQXUVLMhTZuP2LZrGWV8VUvVp+8vi9qmK+7B9lHCkb8
- yh+x2DE6DhzYZfIlH8CYGAmOI79GiqE3TyGgJLphSoomCpKsFYI2q9VcqgvgHEGoRkZPGHjJ
- EPGFISTMkk5VIkWMIRGIiJBBA4Azk8QZLHw6jf1iIqr1V3v3GzlSqccvyMsyOsZOTBs8jevS
- x14Jnzbf7BdiquJnDPRuUFDECxCenKDoOj2LHN2GS1m5RQvG5gwvTJRZSjGWtjotTKdCmkra
- 1zR2WMOLDZO/l1fN/gS6tPBoaZ/hjO+8WfuNsr1W1l+bHI8OsHGWE1GrTp1YJYREyyZy9c+9
- 06L2EwM23ZlsZHez1GrkMsnNtTYp+I1dzbgd9+DetnZ19jswy4v49VuWeh1as99KWZVItzcv
- 4OHU2NU2UwpS/jfhl3FcWnucnCbFVw8TZ6Xm3aNODbUpG6zBTuMObVevJ4WdrfFbrMeJyWYM
- u9exZ2vzPQaaDLzpeqbU6b9JqYdDXa15etqjbqnhs9Lg8vzYbvFpvbV4tF/fm+DusbKaWmzR
- Z1s+FJlSYdZo61zc1UaX+7XL0rqYd7LUazNZ5utbmw5JRolpuWZxGNd9Noycmprj5ltmkd6y
- yUp0KFa7vHl7GiaKb8d27rV62nG9lU4G63TDm0qlk1wzGb4XS5Te6rLP9NTLlMG11mGmsmJV
- 3FlePq4plnV6VOQ4ztVdxVS3FKU6+7orHFqp+lqxe1dP420bLOA4Ow0ceGzJS97t7WS/tVY6
- kpPiP5yVVZ7nZ1b4cztTr9nPkUPzsfHs+dfJrZ+e0zcx9vk6lzLNnE2qSXcH5l09cMAxOYN8
- stkO0dgpOUT+rWB14IblgbmNKNyIWNRDAccl0GhVDEVrnXMgqKsDDMgCpeGEQLTuHyqrF+lu
- 5p/Jn2p0Tsy4P6newwulHD4Kw7vExPXdop7DtX2eHx1bM8LrRTgUXlusfJ3vm7XRk6MuDfKe
- Dzb697/Wn3fNwtanCca1Rx4Wy59HYcO/14e3+zUu7X9vG7V713oYasOCzlkr0rNVLtWz23q9
- 6epbu4bM0qtbcWvRdsqcGLVTBq3bJJbw7PW5QLVahD52yLYc3q5QrQoqqlV12tdh3LOOmo/V
- /0hvIlzY7JPmutRVxV37HvLzFKxUrK6ope0sNEidcP3dB0DT5bkDJA4z6YYpeBeBfOi1JmMU
- xcQqqqGERAk5F7ANET46LJVgN7ZYWjeoHKZEtgiVB9NJzzDOnO0mjXWHNwcKZxfN22s4VFr7
- 1rrr9bbZW3XZuzBnfbdeGkLbPbnbVhui+l7VritrYqaXb5q0mZo1cxfRto14cbcMWqG25qq3
- k73e+T7HoYMj26UWez6Gcfebb8frKx8/XqW46WybNaipIn1UGcEMDoozesCoanJMcM0gWdxy
- MRrJYXMhdZtVcufBtl2dNWeVVzWtpni9fsiij+vi22w/a8el2WHh5AGLdgB2I2TRmskWLA4Z
- rqYCndoy0AGfVM9pzCk2aR4ODHeyyaTMh4P5nu2lrwKGdIFoUdpLznlMS7C//pSyXgsfVlcv
- aySqk20aLsLe/YiIgi8M5gcWMeTQbeutHWJOHeKDmAQRDu/a1bIZc9XMlbcKuHhAbNyJChhk
- 48K3zdvvriqqqrsdpRSl5NNtrXXve5VH59b3eP04uupUpScIeZL0onepLa0hVLGnpw4leWf/
- jS2M2y0s1kqqoqt6Fk9HsWjef7fX2z/y9SdHyWfPN3E+hY2SjAw/6rv0UkmVlvfKTJtCjFw/
- UVJio+M2H6tGEoZ4xyVKikor5R+uJwTmazsPA4Kh30i1IfP6vv3YorytYm8Re0loVP0HttPp
- lSOpJHZzV61lnm+HfZShdqdT7ut56CmrVNZH5CgwUnxKm7fdwbNaj9dWqScrLnptHtrJT2Fm
- aoqVVFi1L2VXp8sQwVJz5qUVULiriyhd5ZeXz2ybz9nX3p4JiOB+EsWKjhC2FzpcWdA6p/77
- fxdXuPfT4OKXovFpwMT0MNF7ZYq1o/Sz9OEY30XlypGpUl4stO1imMJxZLKZqqNFrDgzoviZ
- SlKsJmh8IyqGLRs2Zi74MN12cLHzF2V1MReqil5O3Y63EfTxaFsYcrGLy9E4tZ3DRJiJvPV8
- fY973uKHBNfP3VVO1MqrsVNKSn/edS6YPJNLfr8WZP2mTl7TymVnkpW89bRJ/zoc5qeT1ihS
- 72XNrVKpeHJXrhkuYkruxlV9pOKlnNd6ptG3XJUKVI7xSUntOvRUTjmG57FAh5QSQoQWlQRJ
- RSUEQnGB+YaNbpKTVRLzYxE3MJb3vcVLrlCr1Ve5T3VW5suh6jk2YsdFmk+07nhFUZrBKECx
- Ko3aIMSeZJEQiCRGFJSiooqCqSlT8uLSXlHmqS0WSYlxdKYF7JkqGqup9T22WUs+3qWilxbu
- qfj+3K+ivvbFi1F9ftuvUrl8eDVnSn5R87sr5ye4WOpTAu+g+o5yc6k+VVXF85xeSeL1KUUw
- /k1jxqJz+uRnmmZg7BQ4zP3LWu28jxSyyUpZaftdnbYuvFFVVJHXJI417zeP45k5KqKoqlSH
- dJpHM9RiGHepu8dEnFPom81qST3LaJ5OD+1SnxegcFKKpVKYPqT5cPwT4tJpqmF3UnFkeGBq
- UpSZXcJLl9EsLDgh2MjdVivpKRSjwcZ10edfZ6vwZYZXtYqvx/VrWJmnBGqycJ5JSx1o65HV
- DuJeYk/fWOW9/fTrVLVnMr3VeZkVSg3cFKkOKXsepcqyrFeD8ZdaqrTJdR0NLMFrMXkWXKWm
- JaKlB50WYGy0XzE1nRZKWbSGCpF5eKMSli65iUNmyrCx+VN5QtKEMBwN0KKN0PR6P+5+rz9W
- 93ddauvRPkSQxgaUrslQ6dvbCWVJKVFSopaWQtJoixdPi9Z8UPO8o+r4sLVMv65JPrHBD2Ki
- GELxH46UOUicJFIuZlKWRaH1w+Q+1TpPmdsPsScCdb/iPVJzcUpRntdWP+XZ3MUYI6lpD4LL
- +qyGSp6YlTpLFLJVRFKMvqaOnqNDWa1FUopSo1iXnqt7P00s+/e1OFkm0jaTxTdfjwkkyXg5
- pbzk8YelmT0QrpCvQ4N2G9ouscJeWpPYqNdWVl2imlMMmcsVmxfweOl8LFkUosKa7sfzat1l
- lPu09H3u/wpO/1cxUa81Op0VTRYstKU1OmYaNdYz0lTWrFklkwURu310KLpW0M/iRuaUXllI
- 3ZbMWpL0ReSpZKTxcdV2FehgWaV4KXSpmsVU0sWU405WVaLSzTp0vzorposnBrD11aOuRwQ2
- YRySn4Yp4nVqNpNHCRD8KklKhd/nHfeTKinVC0mpspUqU71lpTKyWqrWFq8Ki6koVFUqUmMw
- nL3dFlRTJ0kkzGqd3uUnwWTxs4fr1xj0ecHKf8OiS52vAtPaPbQ7ke6c3wYlk81PyK5+uST3
- dQxP5w/pDrf0+iQ0DTzffT0Kemzzz540M+frmgo9tSSlQe06nkWvzaLSXzFUvwbLHfQnrko8
- Io/YU5q/o6/979nHjdrOZbZWy8Onro7O0qFuos+UqWfQs7Iau1FvsHCk93tOx950SxD/+LuS
- KcKEhrI8XBA=
- --------------050107030903080507030408
- Content-Type: text/plain; charset="us-ascii"
- MIME-Version: 1.0
- Content-Transfer-Encoding: 7bit
- Content-Disposition: inline
- _______________________________________________
- ccan mailing list
- ccan@ozlabs.org
- https://ozlabs.org/mailman/listinfo/ccan
- --------------050107030903080507030408--
|
